/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  let dummy = new ListNode(-1) // 生成一个新的头结点
  let cur = dummy // 标记头结点作为后续的尾结点
  let p1 = list1
  let p2 = list2
  while (p1 && p2) {
    // 当两个头结点都不是null的时候继续判断
    if (p1.val < p2.val) {
      // 得到最小的
      cur.next = p1 // 拼接到最后
      p1 = p1.next // 头结点后移
    } else {
      // 相同的道理
      cur.next = p2
      p2 = p2.next
    }
    cur = cur.next // 尾结点后移
  }
  if (p1) cur.next = p1 // 处理多余的部分
  if (p2) cur.next = p2
  return dummy.next // 返回新的头结点的下一个作为头结点
}
